package com.cn.algorithm02.class07;

import com.cn.algorithm02.class01.CodeUtil;

import java.util.PriorityQueue;

/***
 * @author: hels
 * @description:  将一个普通数组重排序为堆结构，其时间复杂度为O(N)
 *       T(N) = N/2*1 +  N/4*2 + N/8*3  + N/16*4 + ...
 * 2*T(N) = N +  N/2*2 + N/4*3  + N/8*4 + ...
 * 进行错位相减
 * T(N) = N + N/2 + N/4 + N/8 + N/16 +....
 **/
public class C03_HeapSort {
    public static void main(String[] args) {
        int[] arr = {2,3,1,2,8,5,7,10,3};
        heapSort(arr);
        CodeUtil.printArray(arr);
        System.out.println("===========");

        // 默认是小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(8);
        queue.offer(4);
        queue.offer(4);
        queue.offer(7);
        queue.offer(2);
        queue.offer(4);
        queue.offer(2);
        System.out.println(queue);
        queue.offer(1);
        System.out.println(queue);
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }


    private static void heapify(int[] heap, int index, int heapSize) {
        int left = 2 * index + 1;
        while (left < heapSize) {
            // 找到大的叶子节点
            int larger = left + 1 < heapSize && heap[left+1] > heap[left] ? left+1 : left;
            // 较大叶子节点和根节点比较
            larger = heap[index] >= heap[larger] ? index : larger;
            if (larger == index) {
                break;
            }

            CodeUtil.swap(heap, index, larger);
            index = larger;
            left = 2 * larger + 1;
        }
    }
}
